package com.buaa.leecode;

import com.buaa.leecode.model.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;

public class Util {
    // 获取树的高度
    public int getTreeHeight(String input) {
        double x = Math.log(14) / Math.log(2);
        int height = (int) Math.ceil(x);
        return height;
    }

    public int getTreeHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int left = Integer.MIN_VALUE;
        if (root.left != null) {
            left = getTreeHeight(root.left);
        }
        int right = Integer.MIN_VALUE;
        if (root.right != null) {
            right = getTreeHeight(root.right);
        }
        return 1 + Math.max(left, right);
    }

    private String getValue(TreeNode node) {
        if (node.nodeType == TreeNode.NodeType.NULL) {
            return "null";
        }
        return node.val + "";
    }

    /**
     * 广度优先遍历树，把每一层的值放置在 allLines 数组中，其中 line 是每一层的值集合
     *
     * @param queue
     * @param allLines
     * @param line
     */
    private void bfsTreeNode(int height, LinkedList<TreeNode> queue, ArrayList<ArrayList<String>> allLines, ArrayList<String> line) {
        if (queue.isEmpty()) {
            return;
        }
        TreeNode top = queue.poll();
        if (top.nodeType == TreeNode.NodeType.LINE_END) {
            if (queue.size() > 0) {
                allLines.add(line);
                line = new ArrayList<>();
                queue.add(getLineEndFlagNode());
            }
        } else if (top.nodeType == TreeNode.NodeType.NORMAL) {
            line.add(getValue(top));
            if (top.left != null) {
                queue.add(top.left);
            } else {
                queue.add(getEmptyFlagNode());
            }
            if (top.right != null) {
                queue.add(top.right);
            } else {
                queue.add(getEmptyFlagNode());
            }
        } else if (top.nodeType == TreeNode.NodeType.NULL && allLines.size() < height) {
            line.add(getValue(top));
            queue.add(getEmptyFlagNode());
            queue.add(getEmptyFlagNode());
        }

        bfsTreeNode(height, queue, allLines, line);
    }


    //标记点为每一行的终止符
    private TreeNode getLineEndFlagNode() {
        TreeNode node = new TreeNode(0);
        node.nodeType = TreeNode.NodeType.LINE_END;
        return node;
    }

    //标记空节点
    private TreeNode getEmptyFlagNode() {
        TreeNode node = new TreeNode(0);
        node.nodeType = TreeNode.NodeType.NULL;
        return node;
    }

    /**
     * curno表示需要被填充的字符
     * length表示要填充的长度
     * fillStr表示需要填充的字符
     * 根据要求来填充字符串
     */
    public static String fitStringToLength(String fitFlag, int length, String fillStr) {
        int temp = (length - fillStr.length()) / 2;
        int count = temp / fitFlag.length();
        StringBuilder sb = new StringBuilder(length);

        for (int i = 0; i < count; i++) {
            sb.append(fitFlag);
        }
        sb.append(fillStr);
        for (int i = 0; i < count + 2; i++) {
            sb.append(fitFlag);
        }
        return sb.toString().substring(0, length);
    }

    private void print(ArrayList<ArrayList<String>> allLines, int fitLength) {
        int height = allLines.size();
         String store = "                                                                        ";
         String store2 = "                                                                        ";
        String itemFilter = store2.substring(0, fitLength);
        for (int i = 0; i < height; i++) {
            ArrayList<String> line = allLines.get(i);
            StringBuilder sb = new StringBuilder();
            int linePace = fitLength * ((int) Math.pow(2, height - i - 1) - 1);//每行第一个item缩进字符数
            sb.append(store2.substring(0, linePace));
            int itemPace = fitLength * ((int) Math.pow(2, height - i) - 1);//每个item直接缩进的字符数
            for (int k = 0; k < line.size(); k++) {
                String item = fitStringToLength(store.substring(0, 1), fitLength, line.get(k));
                if (k < 1) {
                    sb.append(item);
                } else {
                    sb.append(store2.substring(0, itemPace));
                    sb.append(item);
                }
            }
            System.out.println(sb);
        }
    }


    public void print(TreeNode root, int fitLength) {
        int height = getTreeHeight(root);
        ArrayList<ArrayList<String>> allLines = new ArrayList<>();
        ArrayList<String> line = new ArrayList<>();
        System.out.println("树的高度：" + height);
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        queue.add(getLineEndFlagNode());
        bfsTreeNode(height, queue, allLines, line);
        System.out.println(allLines);
        print(allLines, fitLength);
    }

    /**
     * 根据输入字符串构建树
     *
     * @param str 格式：5,4,8,11,null,13,4,7,2,null,null,null,1
     *            5
     *            / \
     *            4   8
     *            /   / \
     *            11  13  4
     *            /  \      \
     *            7    2      1
     * @return
     */
    TreeNode buildInput(String str) {
        TreeNode root = null, head = null;
        LinkedList<TreeNode> queue = new LinkedList<>();
        String[] list = str.split(",");
        if (list.length > 0) {
            root = new TreeNode(Integer.parseInt(list[0]));
            queue.add(root);
        } else {
            return null;
        }
        for (int i = 1; i < list.length; i += 2) {
            head = queue.poll();
            if (!list[i].equals("null")) {
                TreeNode left = new TreeNode(Integer.parseInt(list[i]));
                head.left = left;
                queue.add(left);
            }
            if (i + 1 < list.length) {
                if (!list[i + 1].equals("null")) {
                    TreeNode right = new TreeNode(Integer.parseInt(list[i + 1]));
                    head.right = right;
                    queue.add(right);
                }
            }
        }
        return root;
    }

    public int getMaxItemLength(String input) {
        String[] list = input.split(",");
        int re = 0;
        for (int i = 0; i < list.length; i++) {
            if (list[i].length() > re) {
                re = list[i].length();
            }
        }
        if(re%2==0){
            re++;//高度都改成奇数，对齐方便
        }
        return re;
    }


    public static void main(String[] args) {
        String input = "5,4,8,11,null,13456,4,7,2,null,null,null,123456";
        Util solution = new Util();
        int fitLength = solution.getMaxItemLength(input);
        System.out.println("自适应元素打印宽度：" + fitLength);
        TreeNode root = solution.buildInput(input);
        solution.print(root, fitLength);

    }
}
